package com.hzchendou.blog.code.chapter02.example03;

/**
 * 数组寻值.
 *
 * @author hzchendou
 * @date 2022/10/19
 * @since 1.0
 */
public class Example {
    //// 面试题3：二维数组中的查找
    ////题目：在一个二维数据中，每一行都按照从左到右的顺序排序，每一列都按照从上倒下递增的顺序排序
    //// 请完成一个函数，输入这样的二维数组和一个整数，判断数组中是否含有该整数

    /**
     * 在 二维数组 vals 中搜索值 searchVal，
     * 从友上角开始搜索，存在4种情况
     * 1. 搜索位置的值 等于 搜索值，返回 true
     * 2. 搜索位置的值 大于 搜索值, 因为从上到下递增，说明搜索位置所在列的下方值都大于搜索值,
     * 那么可以确定在这一列找不到搜索值，前往前一列进行搜索
     * 3. 搜索位置的值 小于 搜索值，因为从左到右是递增的，算法是从右往左搜索的，
     * 那么可以确定在这一行找不到搜索值，前往下一行进行搜索
     * 4. 如果超出的搜索范围都没有找到，直接返回 false
     *
     * @param vals
     * @param x         当前搜索位置的行号
     * @param y         当前搜索位置的列号
     * @param searchVal 搜索值
     * @return
     */
    public static boolean search(int[][] vals, int x, int y, int searchVal) {
        if (vals == null || x < 0 || x >= vals.length || y < 0 || y >= vals[0].length) {
            return false;
        }
        System.out.format("搜索 %d行, %d列 -> %d, 结果 ", x + 1, y + 1, vals[x][y]);
        if (searchVal == vals[x][y]) {
            System.out.println(" 值等于搜索值");
            return true;
        } else if (searchVal > vals[x][y]) {
            System.out.println(" 值小于搜索值, 该行后续值不存在搜索值,前往下一行搜索");
            return search(vals, x + 1, y, searchVal);
        } else if (searchVal < vals[x][y]) {
            System.out.println(" 值大于搜索值, 该列中的续值不存在搜索值,前往前一列搜索");
            return search(vals, x, y - 1, searchVal);
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] v = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        int x = 0;
        int y = v[0].length - 1;
        int searchVal = 7;
        System.out.format("从数组中查找 %d, 结果: %s", searchVal, search(v, x, y, searchVal));
    }
}
